File created:  910620
1.1 Revised:  911007

qd3d:	A Vividus Source Code Library for Three Dimensional Computer Graphic Primitives

Users must read the license agreement before using this library.  The licensing agreement is found in the file "Vividus Licensing."

Vividus Source Code Library Documentation:
Vividus Source Code Libraries are documented in two locations.  First, every library folder includes a documentation file.  This documentation file discusses general issues related to the library such as common data formats, efficiency considerations, types of routines available, conventions, assumptions, and etc.  The second type of documentation is individual subroutine documentation.  This is included in the subroutine itself.  Vividus recommends obtaining a source code browser to quickly index to subroutine documentation.  One example is PopUpFuncs by Eric Slosser [SciComp Software; 2912 Claremont Ave #21; Berkeley CA 94705]. 

There may appear to be other forms of documentation in the library folder and in the source code itself.  This documentation is mainly for internal Vividus use and developer curiosity.

Revision information and histories are included at the end of this document.

Introduction and Requirements:
Qd3d provides three dimensional drawing primitives.  Features include Gouraud shading, z-buffer hidden surface removal, perspective and parallel projections, wireframe mode, and depth queing.

The qd3d library has been developed with THINKC version 5.0 and uses several of its object oriented extensions.  Qd3d is not compilable by standard C compilers but should be compilable by C++ compilers with minor modifications.  Qd3d requires the vect Vividus Source Code Library.  Most of qd3d execution assumes the presence of Color Quickdraw and, depending on use, may require large amounts of memory.

Installation (for THINKC):
Vividus recommends creating a folder entitled Vividus in the same folder containing the THINKC application.  Copy the qd3d folder, along with vect and any other Vividus Source Code Libraries to this Vividus folder. This allows standard usage of angle brackets when indicating the inclusion of a header file from the THINKC "directory tree."

For projects which use the qd3d library, add all source files associated with the vect library and the following source files from the qd3d folder:

Cqd3dPort.c
qd3dLib.c
gouraud.c
hedra.c
geometry.c

Any files which call a qd3d routine should include the header file Cqd3dPort.h.  The Cqd3dPort.h file contains a class definition for the three dimensional viewport and function prototypes for associated graphics primitives.  Error codes for qd3d are defined in Qd3dErr.h.

Brief Introduction to Three Dimensional Computer Graphics:
This section briefly describes important computer graphics fundamentals as directly related to qd3d.  The following books are recommended for in depth information:

J D Foley, A van Dam, S K Feiner, J F Hughes, Computer Graphics:  Principles and Practice, 2ed, Addison Wesley, 1990.  ISBN 0-201-12110-7.

	This large book is often considered a comprehensive reference for computer graphics.

A Watt, Fundamentals of Three-Dimensional Computer Graphics, Addison Wesley, 1989.  ISBN 0-201-15442-0.

	This book concentrates on rendering issues in computer graphics; lighting models, shading models, and etc.  Material is covered at a very reasonable pace.

Coordinate Systems:
Locations, or points, in space are typically identified by a triplet of numbers.  These numbers are the x, y, and z values of a point with respect to a common Cartesian coordinate system.  See "vect.doc" for a graphical depiction and explanation of the right handed, three-space, Cartesian coordinate system used by qd3d.  The choice of the origin and orientation of this common coordinate system is arbitrary.  Point triplets in reference to this common coordinate system are referred to as world coordinates (WC).

A viewer is placed in the scene by specifying the viewer's location (f).  The viewing direction is the ray from f to a point of attention (a).  The last parameter associated with a view is analogous to the axial twist (sideways or right side up) that a camera is held with.  This axial twist is determined by an up vector (u).  F, a, and u are expressed in relation to the world coordinate system.

Viewing parameters define another useful coordinate system called the eye coordinate system.  Points in reference to this system are referred to as eye coordinates (EC).  The z axis of this coordinate system lies along the ray from f to a.  The y axis lies along the ray determined by u.  The x axis points to the right (from the viewers perspective).  All three of these axis are orthogonal.  Unlike the world coordinate system, the eye coordinate system is left-handed.  The orientation of the z axis is opposite that found in a right-handed coordinate system.  Lengths in world space and eye space are equivalent.

Perspective and Parallel Projections:
Since computer screens are two-dimensional, the three dimensional scene must be projected onto the EC xy plane.  Two main types of projections are perspective and parallel.

Humans find perspective projections more natural.  Close objects appear larger than distant object.  

Parallel projections project points along lines parallel to the EC z axis to points on the EC xy plane.  While parallel projections have engineering uses that perspective projections don't, they tend to appear flat since far objects are no smaller than near objects.

View Volumes, Clipping, and Depth Queing:
Clipping removes picture elements outside the field of view.   Removing unseen picture elements renders a scene more quickly.  Computer graphics typically clip to view volumes as shown in figures 1 and 2.  These diagrams also show the parameters involved with perspective and parallel projections.

The perspective projection view volume frustum is completely defined by the near and far planes, and the viewing angle (v).  The viewing angle may be used as a zoom factor.  The average viewing angle of the human eye is 50¡.















		
		Figure 1b:	Projection of 1a.



Figure 1a:	A perspective view and its viewing volume.


The parallel projection view volume parallelepiped is completely defined by the near and far planes, and the upper left (UL) and lower right (LR) points.  Note that the UL and LR points are in EC.















Figure 2a:	A parallel view and its view volume.	Figure 2b:	Projection of 2a.


Perhaps the most awkward parameters to calculate or estimate are the locations of the near and far planes.  A near plane of 0 and a far plane of ° reflect the practical experience of human sight.  Unfortunately, these choices defeat depth queing and z-buffer hidden surface removal.  Ideally, the near and far planes should be chosen just in front and just behind the nearest and farthest objects of interest.  The near clipping plane may be used to remove the front portion of an object to reveal its interior.  The far plane may also be used in a similar fashion.  Note that the near and far planes are expressed as points along the EC z axis.

Depth queing is a technique which aids in depth perception.  Close objects are drawn in approximately their original color.  Distant objects are drawn with their color blended with the background color.  The relative position of the point being drawn between the near and far planes provides a parameter for the amount of background color blending.

Hidden Surface Removal:
Parallel and perspective projections simply map points to points and do not readily tell if objects overlap.  Two common techniques used to combat this hidden surface removal problem are  the painter's algorithm, and the z-buffer.

The painter's algorithm is very simple and surprisingly efficient.  Picture elements, polygons, are sorted and drawn from back to front -- analogous to how a painter paints near objects on top of more distant objects.  Unfortunately, this technique easily fails.  Polygons which intersect other polygons or polygons which span a large depth of field are typical sources of errors.  Since qd3d does not buffer polygon primitives, the client must sort and draw the polygons in EC back to front order.

The z-buffer is another simple method for hidden surface removal and is integral to many current day engineering workstations.  Z-buffer hidden surface removal maintains two frame buffers.  One frame buffer is for the image and the other is the z-buffer.  There is a one to one correspondence between pixels in the image buffer and elements in the z-buffer.  The element in the z-buffer is the current EC depth of the appropriate image buffer pixel.  Every time a new pixel is written, its new depth is compared with the element found in the z-buffer.  If the new depth is closer, the image buffer pixel and the z-buffer element are replaced by the new values.  If the new depth is farther, the new pixel and depth are discarded  -- it is behind the current pixel.

The z-buffer algorithm handles intersecting polygons, polygons with large depths of field, and polygons drawn in no particular order.  Unfortunately, it requires an additional amount of memory approximately the size of the image buffer.  In addition, the discrete nature of the z-buffer values may produce artifacts in resulting images.  Poor choice of near and far planes emphasizes these artifacts.

Some applications benefit from not hiding hidden surfaces.  The Color Quickdraw drawing modes of addOver, addPin, subOver, and subPin provide enough flexibility to efficiently simulate transparency.  For example, a black background and the addPin mode causes the overlapping regions to have a brighter color -- a simple transparency.

Lighting Models and Shading:
Without a lighting model, three dimensional scenes are limited to wireframe images.  A lighting model takes into consideration object parameters, light sources, and viewing parameters to generate a suitable color for a given point on the object.  Common features of these models include:  object coefficients of reflectivity -- the color of the object; specular and diffuse components -- the glossiness and matteness of objects; ambient intensity -- the background light; and the color and brightness of the light source(s).  Brightness and reflective coefficient components typically range from 0.0 to 1.0.  Many of the models treat light as composed of various combinations of the three primary colors.  While this last assumption is often acceptable, it loses an amount of realism.

Qd3d drawing primitives have little to do with the lighting model.  Rather, they draw polygons with the color already calculated by the lighting model.  It is the responsibility of the client to choose, acquire, and use a lighting model to calculate the appropriate colors.

A simple diffuse lighting model calculates color component intensities by taking the cosine of the angle between a polygon surface and the vector towards the lightsource, and then multiplying this by the light and object reflectivity components.  The ambient intensity is simply added to this diffuse intensity.

The Phong lighting model adds a specular component to the simple diffuse model.  The phong.h and phong.c files included with qd3d provide an implementation and although specifically coded for a single lightsource, the phong routine therein could provide the basis of a multiple lightsource model.

Shading models determine how the color changes across the surface of a polygon.  The simplest shading model colors the polygon one homogeneous color.  The Gouraud shading model bi-linearly interpolates the color of the polygon based on colors specified at the vertices. 

The homogeneous shading model is appropriate for objects whose polygons should appear flat.  The lighting model is used once for the entire polygon and uses the normal of the polygon. 

The Gouraud shading model is used for objects which should appear smooth.  In this case, the lighting model is applied to every vertex of the polygon.  The surface normal used at these vertices is rarely the normal of the polygon but typically an average of the normals of the polygons associated with that vertex.  Gouraud shading is subject to Mach banding and missed specular highlights.  Both of which deter from realism.  To help combat these problems, the object may be broken into smaller polygons.  This in turn increases computational costs.

Speed, Pipelines, and Standards (The Vividus Soapbox):
Computer graphics typically push computer hardware past its edge and has been a driving force in high performance architecture research.  Engineering workstations with three dimensional capability often have several processors arranged in a pipeline and a hardware z-buffer.  Each processor provides an element of rendering a graphic primitive:  one processor performs the WC to EC transformation, the next several processors perform clipping to the viewing volume, the next starts a hardware polygon filler, etc.  Such an architecture allows the real time generation of pictures involving hundreds of polygons.  An image generation rate appreciably smaller than 30 frames per second is merely interactive.

The Macintosh has no three dimensional graphics architecture and as a result, all three dimensional work must be done on a single processor.  Speed can be increased by integrating the three dimensional graphics primitives more closely with the application but this decreases application code maintainability and readability and will not make a dent in the orders of magnitude increase in speed enjoyed by the graphics architectures.  An example of a highly integrated three dimensional viewing program is V3d -- available from the MAUG libraries of CompuServe.  Qd3d architecture promotes separation of application and three dimensional primitives.  This favors the programmer productivity  and software engineering issues.

Currently, there are at least two three-dimensional graphic accelerator boards available in the MS-DOS/PC clone market.  One is produced by an engineering workstation manufacturer which has also recently signed an agreement with a major clone manufacturer.  The retail price of this board is less than twice the retail price of the Macintosh Display Card 8¥24GC.  This may seem expensive, and admittedly it is, but it is quite a deal.  Just a few years ago the manufacturer sold their workstation of comparable graphics performance for twenty times that amount!

Vividus considers three dimensional graphics an enabling technology.  While few mainstream programs require three dimensional graphics now, Vividus believes this is a result of the relative unavailability and slow response times of 3d graphics on 2d architectures.  As 3d graphics become more widespread and quicker, more applications will be developed which will use 3d graphics and do things which can not be done in 2d.  History has shown that much more computing power always becomes available for a much cheaper price.

So why is Vividus on a soapbox?  Perhaps with more pressure and voiced desire from the Macintosh developer society, changes will occur which will promote the availability and marketability of such 3d hardware.  Premier among these changes could be a Three Dimensional Quickdraw Standard.  Such a standard would ensure to hardware developers of 3d graphics boards that applications written using the standard would automatically take advantage of their hardware.  In other words, the 3d hardware manufacturer would be ensured of a market.  Secondly, it would ensure to the 3d software developer that his software would automatically take advantage of any 3d hardware present.  And as a result, the developer's software is able to compete with similar software in the accelerated PC realm.

Standards are more important with the Macintosh.  The MS-DOS/PC clone market is so huge, a company can make a specialized piece of hardware running a specialized piece of software and still find enough customers to make it profitable.  This situation is not nearly as present with the Macintosh.  Hopefully Apple will be firm and un-afraid of offending present 3d developers and define a standard.  If not, the fast 3d graphics market will simply be lost to the PC arena leaving those Macintosh 3d developers fighting with each other and Apple.  In the past Apple has done some things right and Apple has done some things wrong.  This is something Apple needs to do right.  Perhaps they could learn from others successes and mistakes.

If Macintosh 3d hardware doesn't occur, why not just join the MS-DOS/PC clone crowd?  This will always be a sad but serious alternative.

Vividus will gladly consider adopting qd3d to drive any hardware manufacturer's three dimensional board.

From all of this, don't conclude qd3d is a slow Macintosh 3d graphics library.

qd3d Conventions:
All conventions pertaining to the vect library also pertain to qd3d.  Of particular mention are the right-handed Cartesian coordinate system, the spherical coordinate system, the vector data type, and the method for identifying a vector list.  While points and vectors are not mathematically equivalent, the vector data type is used by qd3d to specify points in three space.  The vector datatype is also used to specify colors in qd3d.  X, y and z specify the red, green, and blue components respectively and range from 0.0 (black) to 1.0 (full intensity).

When dealing with composite names, all functions and messages in qd3d capitalize the first letter of each word.  Key words and acronyms to be aware of are: 

Poly -- the operand will consist of an integer count and a pointer to an array of points; 
3d -- all three dimensional drawing primitives include this to distinguish from 2d primitives; and
C3d -- identifies a 3d primitive in which an array of colors is associated with the point list.

The foundation of qd3d is the Cqd3dPort.  A parameter of a Cqd3dPort is read or changed by a message to the Cqd3dPort in question.   Function calls perform drawing primitives.

All drawing occurs in the3dPort -- a global variable pointing to the current Cqd3dPort.  Drawing primitives do not change the attributes of the Quickdraw pen but may change its location.  Polygonal drawing primitives are only defined for planar, convex, non-degenerate polygons with PolyMaxN or fewer counter clockwise ordered vertices.

Errors are reported by the Qd3dError function and method.  The Qd3dError function returns the last reported error for the current Cqd3dPort and the Qd3dError method returns the last reported error for the given Cqd3dPort.  These functions reset the reporting mechanism and not the actual primitives.  The actual primitives only set the error code when an error occurs -- they never clear it. 

Presently only two error codes are defined.  One gives notification of insufficient memory for the z-buffer, and the other gives notification of the present 3d pen location being outside the view volume.

The definitive reference for functions, messages, and error codes is the Cqd3dPort.h file on disk.

The Cqd3dPort:
The class Cqd3dPort defines the three dimensional drawing environment of qd3d.  Messages to the Cqd3dPort class deal with the viewing parameters and rendering options of qd3d.

Cqd3dPort Initialization, Maintenance, and View Parameter Messages:
A Cqd3dPort is created and initialized by the following code:

	your3dPort = new(Cqd3dPort);
	your3dPort->Init();

It's default viewing parameters are:

	f = <6.2735, 6.2735, 6.2735>	(10 units from <a>)
	a = <.5, .5, .5>
	u = + z axis
	perspective view type
	v = 60¡
	OnlyQD = true
	UseZBuff = false
	CullBacks = false
	DepthQue = false (off)
	Wireframe = false (off)

Drawing must not be performed until the Cqd3dPort is told about its QuickDraw environment with SetQDEnviron, what part of that environment to draw to with SetQDRect, a projection is defined with SetPerspective or SetParallel, and the 3d port is told to set itself to the current 3d port with Set3dPort.  SetQDEnviron uses the current QuickDraw grafport or GWorld.  Sample code for view initialization for the current grafport or GWorld:

	double	/*	The "natural" viewing angle in radians:	*/
			viewangle = 50.0 * PI / 180.0,

			/*	The distance from f to a:	*/
			near = sqrt((10.0 - .5) * (10.0 - .5) * 3.0),

			far;

	/*	sqrt(3.0) is the size of the volume of interest
		-- the unit cube.	*/
	far = near + sqrt(3.0);
	near = near - sqrt(3.0);

	your3dPort->SetQDEnviron();
	your3dPort->SetQDRect(&thePort->portRect);
	your3dPort->SetPerspective(viewangle, near, far);
	your3dPort->Set3dPort();
	
Get3dPort returns the current 3d port.  Alternatively, the global variable, the3dPort, may be used.

Additional viewing parameter messages include SetView, SetPolarView, GetView, GetPolarView, GetParallel, GetPerspective, and GetProjectionType.  The message Erase should be used to erase the 3d port to the current background color and reset the associated z-buffer (if being used).

Cqd3dPort Options:
Four options affect the rendering results of nearly every drawing primitive.  They are CullBacks, OnlyQD, UseZBuff, DepthQue, and Wireframe.  All of these options have appropriate Get and Set messages.

If the CullBacks option is on, back facing polygons are never drawn.  The surface normal of a polygon is defined as the cross product of the vectors between the first and second, and second and third vertex.  A positive EC z component in this normal indicates, the viewer sees the front face of the polygon -- the polygon will always be drawn.  A negative EC z component indicates the viewer would see the back face of the polygon -- the polygon is drawn only if CullBacks is off (false).

OnlyQD true causes qd3d to keep from generating any SetCPixel call -- all generated Quickdraw calls are fast 2d lines or 2d polygon fills.  As a result, the picture may be recorded as 2d objects in a PICT memory structure -- the same data structure often used and edited in "draw" programs.  OnlyQD true causes color non-homogeneous 3d primitives to be generated using 2d primitives with a single color.  That single color is the average of the vertex colors.  With OnlyQD off, qd3d is free to call SetCPixel -- the resulting image is only appropriately handled as a pixel map.  UseZBuff requires OnlyQD to be off.

UseZBuff true enables z-buffer usage.  To use the z-buffer, OnlyQD must be false.

DepthQue enables and disables depth queing.  Enabling depth queing also requires a fade color and a far point fade fraction.  Depth queing operates both with homogeneous "3d" color primitives and the "C3d" Gouraud shaded type primitives.  If OnlyQD is true, 2d type primitives are generated with a single color that is the average of the associated depth-qued vertex colors.

Wireframe  maps all fill primitives to frame primitives.

These options greatly effect the speed and quality that images are rendered with.  By having these integral to qd3d, an application which generates Gouraud shaded, z-buffer hidden surface removed images can easily implement a preview mode -- all primitive calls are coded as the "C3d" type and the preview is implemented by simply changing the appropriate options.

qd3d Drawing Primitives:
Mark, Line, Frame, and Fill are the four main types of 3d primitives.  All are of the "Poly" type and all come in the "3d" and "C3d" flavors.  The CullBacks option only affects Frame and Fill primitives.  The Mark primitives have an additional parameter which is a callback for the actual marking function.  Except for the C3d functions, the primitives drawn attempt to use the GWorld's current pen mode, size, and color -- the actual color used depends on the DepthQue and OnlyQD options.

Erase primitives for frame and fills erase the appropriate area or outline to the background color.  Erase primitives are not reccommended for future development -- they do not redraw what lies behind them and screen updating issues should occur at a higher level of abstraction.

MarkPoint, MarkSelectedPoint, and MarkCtrlPoint are three default marking functions.  They respectively draw a single pixel, a small x, and a small square.  CNTRLWDTH, and SLTNWDTH define the size of the x and square respectively.  The parameter passed to the marking function is the location in WC to draw the mark at.

MoveTo3d, and LineTo3d are the three dimensional equivalents of the 2d MoveTo and LineTo.  MoveTo3d repositions the GWorld's pen location -- this may be used to position and draw 2d text.  When using MoveTo3d to position text, Qd3dError must be checked to determine if the point is outside the view volume.

Hedra:
Qd3d drawing primitives are aptly named "primitives" since they merely provide the graphical elements which comprise more complicated objects.  Hedra provides a rudimentary database and set of functions for drawing collections of polygonal planar surfaces.

A connectivity array and an array of world coordinate vertices define a hedra.  The connectivity array is a list of polygonal planar surfaces, or faces.  A list of vertice indices define each face in the face list.  The vertices in a face must be listed in counter-clockwise order when viewed from the "outside" of the face and a face is terminated by the negative of the last vertice.  Note that this convention prevents vertice 0 from being the last vertice in a face.  Example definitions for a simple hedra:

vector CubeVerts[] = {	//	Vertice
	{1.00,	1.00,	1.00},	//	0
	{1.00,	1.00,	0.00},	//	1
	{1.00,	0.00,	0.00},	//	2
	{1.00,	0.00,	1.00},	//	3
	{0.00,	1.00,	1.00},	//	4
	{0.00,	1.00,	0.00},	//	5
	{0.00,	0.00,	0.00},	//	6
	{0.00,	0.00,	1.00}	//	7
};


short	CubeConn[] = {	//	Face
	0, 4, 7, -3,		//	0
	4, 5, 6, -7,		//	1
	5, 1, 2, -6,		//	2
	0, 3, 2, -1,		//	3
	7, 6, 2, -3,		//	4
	5, 4, 0, -1		//	5
};

Figure 3:  A sample hedra cube and its numerical representation.

Hedra operates on the "current hedra" specified by HedraConn and HedraVerts.  HedraConn sets the connectivity array for the current hedra and HedraVerts sets the vertices for the current hedra.  HedraFrame, and HedraFill are the drawing routines for the hedra module.  Hedra2DBBox returns the 2d QuickDraw bounding box of the current hedra.  HedraErase and HedraFrameErase provide erase operations but should be avoided for the same reasons cited for the qd3d erase primitives.  If the viewing parameters or the world coordinates of the vertices change, HedraVerts must be called again before subsequent hedra operations.

Hedra's database does not provide comprehensive support for any but the most basic of three dimensional applications.  More complicated three dimensional databases should be pursued on an application by application basis.  The object programming paradigm provides a possible foundation for such work.

Current Limitations and Shortcomings:
¥	The z-buffer could be cleared more efficiently.
¥	There is no depth queing for poly marking.
¥	The toolbox function SetCPixel is slow -- a work around should be found.
¥	There are no true 3d text primitives.
¥	Clipping is not fully implemented -- it is only performed to the near and far planes and then if one point is outside the view volume, the entire polygon or line segment is thrown away.
¥	Hedra could be more efficient.

Questions:
Feel free to send your e-mail questions and comments.  Please understand that Vividus consultants are busy and will feel an obligation to respond quicker to licensed users.  Vividus may be reached at the following addresses:

	CompuServe:	73067,542
	Internet:	73067.542@compuserve.com
Change History:
This document describes the present 1.1 version of qd3d.  New text in this document from its last revision appears in italics.  For usage descriptions of new features or routines see the appropriate section of this qd3d documentation or the Cqd3dPort.h header file.

Addition and changes to the library for version 1.1:
More support libraries:	Hedra, geometry, and phong are now included as part of qd3d.  This also means these files are now covered under the qd3d licensing agreement.  Phong provides a simple lighting model and geometry's present purpose is support of the Hedra submodule.

QuickDraw environment handling: 	Qd3d no longer requires the presence or explicit use of 32 bit color QuickDraw or the related GWorlds.  SetQdEnviron has replaced Set3dPortGWorld and SetGWRect has been renamed to SetQDRect.  For usage details see the related section of this document.  This change will necessitate modification in client code.

New wireframe mode/option:	Qd3d now support a wireframe mode.

New Get functions:	Many new Get functions have been added which return view related information.  The new functions are: GetPerspective, GetParallel, GetView, GetPolarView, GetProjectionType.  Due to these changes, several of the previous public instance variables are now considered private or protected.

Other modifications and bug fixes:
Cqd3dPorts are now indirect objects and have a Dispose method.

SetPolarView had a bug which would prevent the point of attention from properly being set unless SetView had been previously called.  This has been fixed.	
		
An internal error in Line3dClip and LineC3dClip was fixed.  Previously, they were returning without specifying a value.

The default viewing parameters have been changed.
	
SetQDRect and SetPerpective/SetParallel are less tightly coupled through the internal addition of BuildProj.
		
The formatting style of all method declarations has been changed to be compatible with the class browser.
		
Added Poly3dErase & Poly3dFrameErase.

Modified the phong parameter list to pass vector addresses.

Some "hard" errors now use the  ThinkC exception mechanism.

Error codes, hard and soft, are declared in Qd3dErr.h.